<template>
  <div style="height: 100%; display: flex; flex-direction: column">
    <div class="header traversal-header">
      <el-input placeholder="请输入内容" size="small" v-model="value"></el-input>
      <el-button type="success" size="small" @click="insert" :disabled="isDemo">
        新增
        <i class="el-icon-plus"></i>
      </el-button>
      <el-button type="success" size="small" @click="del" :disabled="isDemo">
        删除
        <i class="el-icon-delete"></i>
      </el-button>
      <el-button type="success" size="small" @click="find" :disabled="isDemo">
        查找
        <i class="el-icon-search"></i>
      </el-button>
      <el-button type="success" size="small" @click="clear">
        清空画布
        <i class="iconfont icon-qingkong" style="font-size: 13px"></i>
      </el-button>
    </div>

    <div class="animate-area" ref="Canvas" id="canvas-container">
      <canvas id="canvas" style="width: 100vh; height: 100vh"></canvas>
    </div>
  </div>
</template>

<script>
import { v4 as uuidv4 } from 'uuid'
import mixin from '@/mixins'
import tree from '@/mixins/tree'
import BTNode from '@/node/BTreeNode'
import Text from '@/node/Text'
import Color from '@/utils/Color'
import Box from '@/node/Box'

export default {
  data() {
    return {
      value: Math.ceil(Math.random() * 1000)
    }
  },

  mounted() {
    this.steps = []
    // 每一步的开始的下标
    this.perStepStarts = []
    // 每一步的结束下标和根节点
    this.perStepEnds = {
      0: undefined
    }
    this.$bus.$emit('setIsPause', false)

    this.rootX = this.$refs.Canvas.clientWidth / 2 - 100

    this.num = 4
  },

  mixins: [mixin, tree],

  methods: {
    insert() {
      let txt = new Text(100, 40, parseInt(this.value), uuidv4(), Color.GREEN_1)
      txt.draw(this.ctx)
      this.insertAimate(txt)
      this.value = Math.ceil(Math.random() * 1000)
      this.perStepEnds[this.steps.length - 1] = this.copyRoot
      this.prePauseOrPlay(false)
    },

    findBTNode(val, txt) {
      let next = this.root
      while (next) {
        this.box = new Box('box', next.x, next.y, next.getRectWidth(), next.height)
        this.steps.push([...this.nodes, ...this.texts, this.box, txt])
        let i = 0
        for (; i < next.keyVal.length; i++) {
          if (val < next.keyVal[i]) {
            break
          } else if (val === next.keyVal[i]) {
            next.texts[i].color = 'red'
            this.addSteps(this.box, txt)
            return { node: next, index: i }
          }
        }
        next = next.child[i]
      }
      return { node: next, index: -1 }
    },

    addSteps(...args) {
      this.copyRoot = this.root.deepCopyAll()
      this.nodes = []
      this.texts = []
      this.copyRoot.getAll(this.nodes, this.texts)
      // 跳过这一步
      this.steps.push([...this.nodes, ...this.texts, ...args])
    },

    insertAimate(txt) {
      let { value: val } = txt
      if (!this.root) {
        this.steps.push([txt.deepCopy()])
        this.perStepStarts.push(this.steps.length - 1)
        this.root = new BTNode(this.rootX, 70, uuidv4())
        this.root.insertInKeyVal(0, val, txt.deepCopy())
        this.addSteps()
        return
      }
      this.addSteps(txt)
      this.curStep++
      this.perStepStarts.push(this.steps.length - 1)

      let { index } = this.findBTNode(val, txt)
      if (index >= 0) {
        let tip = new Text(this.rootX + 100, 40, '已经存在' + val + ',插入失败!', 'tip', 'red')
        this.steps.push([...this.nodes, ...this.texts, tip])
        return
      }

      let next = this.root
      while (next.child[0]) {
        let i = 0
        for (; i < next.keyVal.length; i++) {
          if (next.keyVal[i] >= val) {
            break
          }
        }
        next = next.child[i]
      }

      // 此时的next节点就是叶子节子了
      // 将val数值插入到next节点合适的位置
      let i = next.keyVal.length - 1
      for (; i >= 0; i--) {
        if (next.keyVal[i] > val) {
          next.keyVal[i + 1] = next.keyVal[i]
        } else {
          break
        }
      }
      // i这个位置就是val存放的位置
      // next.keyVal[i + 1] = val
      next.insertInKeyVal(i + 1, val, txt.deepCopy())
      this.root.calcNodeCoordinates(this.rootX)
      this.addSteps()

      if (next.keyVal.length === this.num) {
        // 需要分裂调整
        this.adjustAfterInsert(next)
      }
    },

    // 插入后分裂调整
    adjustAfterInsert(node) {
      // 分裂的下标
      let target = Math.floor((this.num - 1) / 2)

      while (node.keyVal.length === this.num) {
        // 父亲节点
        let parent = node.parent
        let left = new BTNode(node.x, node.y, uuidv4())
        let right = new BTNode(node.x + (target + 1) * node.width, node.y, uuidv4())

        let leftIndex = 0
        let rightIndex = target + 1

        while (leftIndex < target) {
          // left.keyVal[leftIndex] = node.keyVal[leftIndex]
          left.insertInKeyVal(leftIndex, node.keyVal[leftIndex], node.texts[leftIndex].deepCopy())
          if (node.child[leftIndex]) {
            left.child[leftIndex] = node.child[leftIndex]
            node.child[leftIndex].parent = left
          }
          leftIndex++
        }
        if (node.child[leftIndex]) {
          node.child[leftIndex].parent = left
          left.child[leftIndex] = node.child[leftIndex]
        }
        left.parent = parent
        let start = 0
        while (rightIndex < node.keyVal.length) {
          // right.keyVal[start] = node.keyVal[rightIndex]
          right.insertInKeyVal(start, node.keyVal[rightIndex], node.texts[rightIndex].deepCopy())
          if (node.child[rightIndex]) {
            node.child[rightIndex].parent = right
            right.child[start] = node.child[rightIndex]
          }
          rightIndex++
          start++
        }

        if (node.child[rightIndex]) {
          node.child[rightIndex].parent = right
          right.child[start] = node.child[rightIndex]
        }
        right.parent = parent

        if (!parent) {
          let root = new BTNode(node.x, node.y, uuidv4())
          root.insertInKeyVal(
            root.keyVal.length,
            node.keyVal[target],
            node.texts[target].deepCopy()
          )

          root.child[0] = left
          root.child[1] = right
          left.parent = root
          right.parent = root
          this.root = root
          this.addSteps('skip')
          this.root.calcNodeCoordinates(this.rootX)
          this.addSteps()
          break
        }

        // child数组存储node节点的下标
        let i = 0
        while (i < parent.child.length) {
          if (node === parent.child[i]) {
            break
          }
          i++
        }

        // 节点往后移
        let j = parent.child.length
        while (j > i) {
          parent.child[j] = parent.child[j - 1]
          j--
        }

        // 值往后移
        j = parent.keyVal.length
        while (j > i) {
          parent.keyVal[j] = parent.keyVal[j - 1]
          j--
        }

        // parent.keyVal[j] = node.keyVal[target]
        parent.insertInKeyVal(j, node.keyVal[target], node.texts[target].deepCopy())
        parent.child[i] = left
        parent.child[i + 1] = right
        this.root.calcNodeCoordinates(this.rootX)
        this.addSteps()

        node.parent = undefined
        node = parent
      }
    },

    del() {
      let val = parseInt(this.value)
      let txt = new Text(100, 40, parseInt(this.value), uuidv4(), 'red')
      txt.draw(this.ctx)
      this.addSteps(txt)
      this.curStep++

      let { node, index } = this.findBTNode(val, txt)
      if (!node) {
        let tip = new Text(this.rootX + 100, 40, '不存在' + val + ',删除失败!', 'tip', 'red')
        this.steps.push([...this.nodes, ...this.texts, tip])
        return
      }
      let previosNode = this.findPreviousNode(node, index)

      if (previosNode) {
        // node.keyVal[index] = previosNode.keyVal[previosNode.keyVal.length - 1]
        node.updateInKeyVal(
          index,
          previosNode.keyVal[previosNode.keyVal.length - 1],
          previosNode.texts[previosNode.keyVal.length - 1].deepCopy()
        )
        node = previosNode
        // node.keyVal.splice(previosNode.keyVal.length - 1, 1)
        node.splice(previosNode.keyVal.length - 1)
      } else {
        // node.keyVal.splice(index, 1)
        node.splice(index)
      }
      this.root.calcNodeCoordinates(this.rootX)
      this.addSteps()
      this.adjustAfterDel(node)

      this.perStepEnds[this.steps.length - 1] = this.copyRoot
    },

    // 删除后进行调整
    adjustAfterDel(node) {
      if (node.keyVal.length >= Math.floor((this.num - 1) / 2)) {
        // 符合B树的定义，直接返回
        return
      }

      if (!node.parent) {
        // 已经是根节点了
        if (!node.keyVal.length) {
          this.root = node.child.shift()
          if (this.root) {
            this.root.parent = undefined
            this.root.calcNodeCoordinates(this.rootX)
            this.addSteps()
          } else {
            this.steps.push([])
          }
        }
        return
      }

      // 需要进行下溢处理
      let index = this.findInParentIndex(node)

      if (index > 0) {
        // 问问左兄弟有没有得借
        let leftBrother = node.parent.child[index - 1]
        if (leftBrother.keyVal.length > Math.floor((this.num - 1) / 2)) {
          // 左兄弟有得借
          // node.keyVal.unshift(node.parent.keyVal[index - 1])
          node.unshift(node.parent, index - 1)
          // 左兄弟的某个值当家
          // node.parent.keyVal[index - 1] = leftBrother.keyVal.pop()
          let { keyVal, txt } = leftBrother.pop()
          node.parent.updateInKeyVal(index - 1, keyVal, txt.deepCopy())

          let leftBrotherChild = leftBrother.child.pop()
          if (leftBrotherChild) {
            node.child.unshift(leftBrotherChild)
            leftBrotherChild.parent = node
          }
          this.root.calcNodeCoordinates(this.rootX)
          this.addSteps()
          return
        }
      }
      // 左兄弟没得借, 问问右兄弟有没有得借
      if (index < node.parent.keyVal.length) {
        let rightBrother = node.parent.child[index + 1]
        if (rightBrother.keyVal.length > Math.floor((this.num - 1) / 2)) {
          // 右兄弟有得借
          // node.keyVal.push(node.parent.keyVal[index])
          node.push(node.parent, index)

          // node.parent.keyVal[index] = rightBrother.keyVal.shift()
          let { keyVal, txt } = rightBrother.shift()
          node.parent.updateInKeyVal(index, keyVal, txt.deepCopy())

          let rightBrotherChild = rightBrother.child.shift()
          if (rightBrotherChild) {
            node.child.push(rightBrotherChild)
            rightBrotherChild.parent = node
          }
          this.root.calcNodeCoordinates(this.rootX)
          this.addSteps()
          return
        }
      }
      this.dealWithNothingToBorrow(node, index)
    },

    // 处理左右都没得借的情况
    dealWithNothingToBorrow(node, inParentIndex) {
      let parent = node.parent
      // 以下代码是考虑左右兄弟都没得借的情况
      if (inParentIndex === 0) {
        // 最左边的孩子节点
        let rightBrother = parent.child[inParentIndex + 1]
        // 需要根右边的兄弟节点进行合并，就相当于父亲少了一个分支，因此父亲需要下溢一个值
        // let downVal = parent.keyVal.shift()
        let { keyVal, txt } = parent.shift()

        // node.keyVal.push(downVal)
        node.push2(keyVal, txt.deepCopy())

        // rightBrother.keyVal.unshift(...node.keyVal)
        rightBrother.unshift2(node)

        rightBrother.child.unshift(...node.child)
        // 更新node子节点的父亲指向为rightBrother
        for (let i = 0; i < node.child.length; i++) {
          node.child[i].parent = rightBrother
        }
        // 父亲少一个分支
        parent.child.shift()
        node.parent = undefined

        this.root.calcNodeCoordinates(this.rootX)
        this.addSteps()
      } else {
        // 根inParentIndex === 0 是一个左右相反的操作，右边跟左边合并
        let leftBrother = parent.child[inParentIndex - 1]

        let { keyVal, txt } = parent.pop()
        // let downVal = parent.keyVal.splice(inParentIndex - 1, 1)[0]

        node.keyVal.unshift(keyVal)
        node.texts.unshift(txt.deepCopy())
        node.setTextXY()

        leftBrother.keyVal.push(...node.keyVal)

        let texts = []
        leftBrother.texts.forEach(txt => {
          texts.push(txt.deepCopy())
        });

        leftBrother.texts.push(...texts)
        leftBrother.setTextXY()

        leftBrother.child.push(...node.child)
        // 更新node子节点的父亲指向为leftBrother
        for (let i = 0; i < node.child.length; i++) {
          node.child[i].parent = leftBrother
        }
        parent.child.splice(inParentIndex, 1)
        node.parent = undefined

        this.root.calcNodeCoordinates(this.rootX)
        this.addSteps()
      }

      // 父亲的keyVal少了一个值，有可能会导致parent.keyVal.length < Math.floor()
      // 这里其实就是向上递归的过程
      node = parent
      this.adjustAfterDel(node)
    },

    // 寻找node节点在父节点child中的下标
    findInParentIndex(node) {
      let parent = node.parent
      for (let i = 0; i < parent.child.length; i++) {
        if (node === parent.child[i]) {
          return i
        }
      }
      return -1
    },

    findPreviousNode(node, index) {
      let childNode = node.child[index]
      let preNode = childNode
      while (childNode) {
        this.box = new Box(
          'box',
          childNode.x,
          childNode.y,
          childNode.getRectWidth(),
          childNode.height
        )
        this.steps.push([...this.nodes, ...this.texts, this.box])
        preNode = childNode
        childNode = childNode.child[childNode.child.length - 1]
      }
      return preNode
    },

    find() {}
  }
}
</script>

<style lang="scss" scoped>
.traversal-header {
  display: flex;

  align-items: center;

  > .el-input {
    width: 500px;
  }

  .el-button {
    height: 32px;
    margin-left: 10px;
  }

  .el-select {
    width: 110px;
  }
}

.animate-area {
  flex: 1;
}
</style>
